/********************************
* 2、编写一个非递归算法，统计二叉
* 树中度为0、1、2三类结点的数量，
* 并验证是否与性质3结论相同。
**********************************/

#include<stdio.h>
#include<malloc.h>

typedef struct TREE tree;
struct TREE{
    long long data;
    tree* p;
    tree* left;
    tree* right;
};

tree* new_tree(){
    tree* t = malloc(sizeof(tree));
    t->left = t->right = t->p = NULL;
    return t;
}

void print_tree(const tree* t){
    if(t==NULL){putchar('*');return;}
    printf("(%d",t->data);
    if(t->left==NULL && t->right==NULL){putchar(')');return;}
    print_tree(t->left);
    print_tree(t->right);
    putchar(')');
}

// assuming only positive integers
// e.g. (1 ( 2 (4) () ) ( 3 () (5) ) ) where * stands for empty,like ()
// (1(2(4(8)(9))(5(10)(11)))(3(6(12)(13))(7(14)(15))))
tree* build_tree_from_nested_expression(char* s){
    //printf("starting at %c\n",*s);
    char *cursor,*left_start,*right_start;
    int left = 0,right = 0,acc=0,value=0;
    cursor = s;
    while(1){
        // printf("[%c] left=%d right=%d acc=%d value=%d\n",*cursor,left,right,acc,value);
        if(*cursor=='('){left++;if(left==2&&right==0){left_start = cursor;/*printf("left_start=%c\n",*left_start);*/}
        if(left-right==2&&right>0){right_start=cursor;/*printf("right_start=%c break now\n",*right_start);*/break;} }
        if(*cursor==')'){right++;}
        if(value==0){ if(*cursor>='0'&&*cursor<='9'){acc*=10;acc+=*cursor-'0';}else{value=acc;}}
        if(left==right){if(value){tree* root = new_tree();root->data=value;/*printf("Leaf node [%d]\n",value);*/return root;}else{/*printf("Nil\n");*/return NULL;}}
        cursor++;
    }
    tree* root = new_tree();
    root->data = value;
    /*printf("Non-leaf node [%d]\n",value);*/
    root->left = build_tree_from_nested_expression(left_start);
    root->right = build_tree_from_nested_expression(right_start); 
    if(root->left!=NULL)root->left->p = root;
    if(root->right!=NULL)root->right->p = root;
    return root;
}

void cal_degree_non_recursive(const tree* t){
    if(t==NULL)return;
    int zero=0,one=0,two=0,tmp=0,ip=0;// 1-left 2-right 0-p
    const tree* sp[1024];
    const tree* cur;
    sp[ip++] = t;
    while(ip){
        cur = sp[--ip];
        tmp = (cur->left!=NULL) + (cur->right!=NULL);
        if(tmp==0)zero++;if(tmp==1)one++;if(tmp==2)two++;
        if(cur->left!=NULL)sp[ip++]=cur->left;
        if(cur->right!=NULL)sp[ip++]=cur->right;
    }
    printf("[0]%d [1]%d [2]%d\n",zero,one,two);
}

void swap_left_right_non_recursive(tree* t){
    if(t==NULL)return;
    int ip=0;
    tree* sp[1024];
    tree* cur;
    tree* tmp;
    sp[ip++] = t;
    while(ip){
        cur = sp[--ip];
        if(cur->left!=NULL)sp[ip++]=cur->left;
        if(cur->right!=NULL)sp[ip++]=cur->right;
        tmp = cur->left;
        cur->left = cur->right;
        cur->right = tmp;
    }
}

void bfs(const tree* t){
    if(t==NULL)return;
    int left=0,right=0;
    const tree* q[1024];
    const tree* cur;
    q[right++] = t; right %= 1024;
    while(left!=right){
        cur = q[left++]; left %= 1024;
        printf("%d ",cur->data);
        if(cur->left!=NULL){q[right++]=cur->left; right %= 1024;}
        if(cur->right!=NULL){q[right++]=cur->right; right %= 1024;}
    }
}

void tree_del(tree* t){
    if(t==NULL)return;
    if(t->left!=NULL)tree_del(t->left);
    if(t->right!=NULL)tree_del(t->right);
    free(t);
}




int main(){
    char buffer[1024];
    char buf; char* p = buffer;
    while( '\n'!= (buf = getchar() ) )*p++=buf;
    *p = '\0';
    tree* t = build_tree_from_nested_expression(buffer);
    printf("Get tree: ");print_tree(t);putchar('\n');
    printf("Cal degree: ");cal_degree_non_recursive(t);
    printf("Traverse: ");bfs(t);putchar('\n');
    swap_left_right_non_recursive(t);
    printf("After swap: ");print_tree(t);putchar('\n');
    tree_del(t);
    return 0;
}